//获得两数最大公约数(欧几里德算法)
int getGCD(int num1, int num2)
{
	int tmp, gcd;
	do {
		tmp = num1 % num2;
		num1 = num2;
		num2 = tmp;
		gcd = num1;
	} while (tmp != 0);
	return gcd;
}

//获得两数最大公约数(短除法)
int getGCD(int num1, int num2)
{
	int gcd = 1;
	for (int i = 2; i <= num1 && i <= num2; i++)
	{
		//此处不能用if语句
		while (!(num1 % i) && !(num2 % i))
		{
			gcd *= i;
			num1 /= i;
			num2 /= i;
		}
	}
	return gcd;
}

//获得两数最小公倍数
int getLCM(int num1, int num2)
{
	int gcd;
	gcd = getGCD(num1, num2);
	return (num1 * num2) / gcd;
}

//四舍五入，digit参数取{...,0.01,0.1,1,10,100,...}
double round(double num, double digit)
{
	if (digit > 0.0)
	{
		digit = 1 / digit;
	}

	if (num >= 0.0)
	{
		num = (int)(num * digit + 0.5) / digit;
	}
	else
	{
		//0除比0小的负数为什么等于-0？？？
		num = (int)(fabs(num * digit) + 0.5) / (-digit);
	}
	return num;
}

//判断素数
bool judgePrimeNum(int num)
{
	int sum = 0;
	for (int i = 1; i <= num; i++)
	{
		if (num % i == 0)
		{
			sum += i;
		}
	}

	if (sum == num + 1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//判断回文数
bool judgePalindromeNum(int num)
{
	int tmp, sum = 0, numTmp = num;
	for (; num; )
	{
		tmp = num % 10;
		sum = sum * 10 + tmp;
		num /= 10;
	}
	if (numTmp == sum)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//冒泡排序法
template <typename Type>
void bubbleSort(Type* a, int size)
{
	for (int i = 1; i < size; i++)
	{
		for (int j = size - 1; j >= i; j--)
		{
			Type tmp;
			if (*(a + j) < *(a + j - 1))
			{
				tmp = *(a + j - 1);
				*(a + j - 1) = *(a + j);
				*(a + j) = tmp;
			}
		}
	}
}

//选择排序法
template <typename Type>
void selectSort(Type* a, int size)
{
	Type tmp;
	int flg;
	for (int i = 0; i < size - 1; i++)
	{
		tmp = *(a + i);
		flg = i;
		for (int j = i + 1; j < size; j++)
		{
			if (*(a + j) < tmp)
			{
				tmp = *(a + j);
				flg = j;
			}
		}
		*(a + flg) = *(a + i);
		*(a + i) = tmp;
	}
}

//交换排序法
template <typename Type>
void swapSort(Type* a, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		for (int j = i + 1; j < size; j++)
		{
			Type tmp;
			if (*(a + j) < *(a + i))
			{
				tmp = *(a + i);
				*(a + i) = *(a + j);
				*(a + j) = tmp;
			}
		}
	}
}

//插入排序法
template <typename Type>
void insertSort(Type* a, int size)
{
	Type tmp;
	int flg;
	for (int i = 1; i < size; i++)
	{
		tmp = *(a + i);
		flg = i - 1;
		while (flg >= 0 && tmp < *(a + flg))
		{
			*(a + flg + 1) = *(a + flg);
			flg--;
		}
		*(a + flg + 1) = tmp;
	}
}